﻿using System;
using System.Collections.Generic;
using Excel = Microsoft.Office.Interop.Excel;

namespace BloomFilterTest
{
    class Program
    {
        const float TicksPerMilli = TimeSpan.TicksPerMillisecond;

        static void Main(string[] args)
        {
            Excel.Application myApp = new Excel.Application();
            myApp.Workbooks.Add(Excel.XlWBATemplate.xlWBATWorksheet);
            myApp.Visible = true;

            myApp.Cells.NumberFormat = "@";
            myApp.Cells[1, 1] = "trial";
            myApp.Cells[1, 2] = "Add Times";
            myApp.Cells[1, 3] = "Search Times";
            string inputSizeString = null;
            int inputSize;
            float[] addTimes = new float[] { 1000000, 0, 0 }; //0-shortest, 1-average, 2-longest running time
            float[] searchTimes = new float[] { 1000000, 0, 0 }; //0-shortest, 1-average, 2-longest running time
            do
            {
                if (inputSizeString != null)
                    Console.WriteLine("Invalid input! Try again.");
                Console.WriteLine("What size input list?");
                inputSizeString = Console.ReadLine();
                Console.WriteLine();
            }
            while (!Int32.TryParse(inputSizeString, out inputSize) || inputSize < 0);

            int numbersRead = 0;
            int collisionCount = 0;
            float error = bestErrorRate(inputSize);
            int k = bestK(inputSize, error);
            int m = bestM(inputSize, error);
            BloomFilter bloom = new BloomFilter(m, k);
            List<String> dataList = generateRandomDataList(inputSize);

            foreach (string input in dataList)
            {
                numbersRead++;
                long ticks = DateTime.Now.Ticks;

                bool collision = bloom.Add(input);

                float time = (DateTime.Now.Ticks - ticks) / TicksPerMilli;

                myApp.Cells[1 + numbersRead, 1] = numbersRead;
                myApp.Cells[1 + numbersRead, 2] = time;

                AddTime(ref addTimes, time);
                if (collision)
                    collisionCount++;

                Console.WriteLine("{0}% complete", (float)((float)numbersRead / (float)inputSize) * 100);
            }
            FixTimes(ref addTimes, numbersRead);

            List<String> queryList = generateRandomDataList(inputSize);

            numbersRead = 0;
            int matches = 0;

            foreach (string input in queryList)
            {
                numbersRead++;
                long ticks = DateTime.Now.Ticks;

                bool match = bloom.Contains(input);

                float time = (float)(DateTime.Now.Ticks - ticks) / TicksPerMilli;

                myApp.Cells[1 + numbersRead, 3] = time;

                AddTime(ref searchTimes, time);
                if (match)
                    matches++;

                Console.WriteLine("{0}% complete", (float)((float)numbersRead / (float)inputSize) * 100);
            }
            FixTimes(ref searchTimes, numbersRead);



            Console.WriteLine("{0} numbers read", numbersRead);
            Console.WriteLine("{0} Bloom collisions", collisionCount);
            Console.WriteLine("False positive rate = {0}%", 100 * (double)collisionCount / numbersRead);
            Console.WriteLine("Best Error Rate: {0}; Best k: {1}; Best m: {2}", error, k, m);
            Console.WriteLine("\nFastest Add Running Time: {0} ms", addTimes[0]);
            Console.WriteLine("Longest Add Running Time: {0} ms", addTimes[2]);
            Console.WriteLine("Average Add Running Time: {0} ms\n", addTimes[1]);
            Console.WriteLine("Fastest Search Running Time: {0} ms", searchTimes[0]);
            Console.WriteLine("Longest Search Running Time: {0} ms", searchTimes[2]);
            Console.WriteLine("Average Search Running Time: {0} ms", searchTimes[1]);
            Console.WriteLine("Total matches: {0}", matches);
            Console.ReadLine();
        }

        private static void FixTimes(ref float[] times, int numbersRead)
        {
            times[1] = times[1] / numbersRead;
        }

        private static void AddTime(ref float[] times, float ticks)
        {
            times[1] += ticks;
            if (times[0] == times[2] && times[0] == 0)
            {
                times[0] = times[2] = ticks;
                return;
            }
            if (times[0] > ticks)
                times[0] = ticks;
            else if (times[2] < ticks)
                times[2] = ticks;
        }

        private static List<String> generateRandomDataList(int capacity)
        {
            List<String> inputs = new List<string>(capacity);
            for (int i = 0; i < capacity; i++)
            {
                inputs.Add(Guid.NewGuid().ToString());
            }
            return inputs;
        }

        private static int bestK(int capacity, float errorRate)
        {
            return (int)Math.Round(Math.Log(2.0) * bestM(capacity, errorRate) / capacity);
        }

        private static int bestM(int capacity, float errorRate)
        {
            return (int)Math.Ceiling(capacity * Math.Log(errorRate, (1.0 / Math.Pow(2, Math.Log(2.0)))));
        }

        private static float bestErrorRate(int capacity)
        {
            float c = (float)(1.0 / capacity);
            if (c != 0)
                return c;
            else
                return (float)Math.Pow(0.6185, int.MaxValue / capacity);
        }
         
    }
}
